<chapter xml:id="bounded_vector.h">
<title><tt>__vic/bounded_vector.h</tt></title>

<chapter xml:id="bounded_vector">
<title><tt>bounded_vector</tt></title>
<code-block lang="C++"><![CDATA[
template<class T>
class bounded_vector : private non_copyable
{
public:
    using value_type     = T;
    using iterator       = ]]><nt>&lt;implementation-defined></nt><![CDATA[;
    using const_iterator = ]]><nt>&lt;implementation-defined></nt><![CDATA[;

    bounded_vector();
    explicit bounded_vector(size_t max_size);
    ~bounded_vector();

    // BEGIN C++11
    bounded_vector(bounded_vector &&o) noexcept;
    bounded_vector &operator=(bounded_vector &&o) noexcept;
    template<class... Args> T &emplace_back(Args &&... args)
    // END C++11

    // size in objects
    size_t size() const;
    size_t capacity() const;
    bool full() const;
    bool empty() const;

    void recreate(size_t new_max_size, bool size_exact = false);
    void *alloc(); // returns pointer to memory for object allocation
    void push_allocated(); // adds last allocated object to the container
    void pop_back();
    void clear();
    void swap(bounded_vector &o) noexcept;

    // element access
    T &operator[](size_t i);
    iterator begin();
    iterator end();
    T &front();
    T &back();

    const T &operator[](size_t i) const;
    const_iterator begin() const;
    const_iterator end() const;
    const_iterator cbegin() const;
    const_iterator cend() const;
    const T &front() const;
    const T &back() const;
};
template<class T>
void swap(bounded_vector<T> &o1, bounded_vector<T> &o2) noexcept;
]]></code-block>

<p>The standard containers in C++98 don't allow to store non-copiable elements.
Even in C++11 elements of containers like <tt>std::vector</tt> have to be at
least noexcept movable. This class solves the problem. It is a dynamic array
for non-copyable objects or just <tt>std::vector</tt> without autogrowing
<tt>capacity()</tt>.</p>

<p>Without <tt>emplace_back()</tt> it is impossible to create arbitrary new
object right in the container's memory. C++98 lacks forwarding references so it
is ear impossible to pass arbitrary parameters to the element's constructor.
<tt>bounded_vector</tt> overcomes this problem using the following mechanism.
The new element is created using several phases:</p>
<list style="numbered">
    <item>Requesting memory for the new element in the container -
        <tt>alloc()</tt>,</item>
    <item>Creation of the object using placement new -
        <tt>new(ptr) type(...)</tt>,</item>
    <item>Fixation of the newly created object in the container -
        <tt>push_allocated()</tt>.</item>
</list>
<p>See the example at the end of the article.</p>

<p>Maximum capacity is specified on creation of the container. Later it
can be changed but all the elements has to be destroyed before. In other words,
the container can be recreated (<tt>recreate()</tt> function).</p>

<p>When available, <tt>emplace_back()</tt> must be used for elements creation.
If not, the unsafe interface described above must be used with care. It is very
ugly and error-prone but solves the task. After the element is created in the
container, you operate with it almost as easy as with any other copyable object
in the standard container. Anyway, it is more efficient and convenient to use
in general than alternative approaches like creating the objects on the free
store and placing only pointers to the container, even if we have
<tt>std::unique_ptr</tt> to manage lifetime of the objects.</p>

<p>Fundamental differences from <tt>std::vector</tt>:</p>
<list style="numbered">
    <item>Elements don't have to be copyable or movable (<tt>std::vector</tt>
        requires at least noexcept-movability);</item>
    <item>Elements have stable addresses after addition of new element;</item>
    <item><tt>emplace_back()</tt> has precondition (<tt>!full()</tt>).</item>
</list>

<section><title>Class members</title>

<synopsis>
<prototype>typename value_type</prototype>
<p>Type of the elements.</p>
</synopsis>

<synopsis>
<prototype>typename iterator</prototype>
<prototype>typename const_iterator</prototype>
<p>Iterators.</p>
</synopsis>

<synopsis>
<prototype>bounded_vector()</prototype>
<p>Create the object without memory allocation.</p>
<postcondition><tt>capacity() == 0</tt></postcondition>
</synopsis>

<synopsis>
<prototype>explicit bounded_vector(size_t max_size)</prototype>
<p>Allocates memory for <tt>max_size</tt> elements.</p>
<postcondition><tt>capacity() == max_size</tt></postcondition>
</synopsis>

<synopsis>
<prototype>~bounded_vector()</prototype>
<p>Calls <tt>clear()</tt>.</p>
</synopsis>

<synopsis>
<prototype>bounded_vector(bounded_vector &amp;&amp;o) noexcept <badge>C++11</badge></prototype>
<prototype>bounded_vector &amp;operator=(bounded_vector &amp;&amp;o) noexcept <badge>C++11</badge></prototype>
<p>Move operations for C++11 mode.</p>
</synopsis>

<synopsis>
<prototype>size_t size() const</prototype>
<prototype>size_t capacity() const</prototype>
<p>Current size and capacity of the container.</p>
</synopsis>

<synopsis>
<prototype>bool empty() const</prototype>
<p>Returns <tt>size() == 0</tt>.</p>
</synopsis>

<synopsis>
<prototype>bool full() const</prototype>
<p>Returns <tt>size() == capacity()</tt>.</p>
</synopsis>

<synopsis>
<prototype>void recreate(size_t new_max_size, bool size_exact = false)</prototype>
<p>Recreates the container. At first calls <tt>clear()</tt>, then reallocates
memory buffer if <tt>new_max_size > capacity()</tt> or <tt>size_exact</tt> is
<tt>true</tt> and <tt>new_max_size != capacity()</tt>.</p>
<postcondition><tt>capacity() >= new_max_size &amp;&amp; empty() == true</tt>
(if <tt>size_exact == true</tt> then <tt>capacity() == new_max_size &amp;&amp;
empty() == true</tt>)</postcondition>
</synopsis>

<synopsis>
<prototype>void *alloc()</prototype>
<p>Returns the raw memory block where new instance of <tt>value_type</tt>
can be allocated.</p>
<precondition><tt>!full()</tt></precondition>
<note>Use <tt>emplace_back()</tt> in C++11 mode.</note>
</synopsis>

<synopsis>
<prototype>void push_allocated()</prototype>
<p>This call right after <tt>alloc()</tt> adds the just created object to the
container.</p>
</synopsis>

<synopsis>
<prototype>template&lt;class... Args> T &amp;emplace_back(Args &amp;&amp;... args) <badge>C++11</badge></prototype>
<p>Constructs new object and adds it to the container (<tt>alloc()</tt> +
<tt>new</tt> + <tt>push_allocated()</tt> with a single call). A reference to
the new object is returned.</p>
<precondition><tt>!full()</tt></precondition>
</synopsis>

<synopsis>
<prototype>void pop_back()</prototype>
<p>Remove the last element from the container.</p>
<precondition><tt>!empty()</tt></precondition>
</synopsis>

<synopsis>
<prototype>void clear()</prototype>
<p>Destroys the elements in the reverse order they were created.</p>
<postcondition><tt>size() == 0</tt> (<tt>empty() == true</tt>)</postcondition>
</synopsis>

<synopsis>
<prototype>void swap(bounded_vector &amp;o)</prototype>
<prototype><![CDATA[template<class T> void swap(bounded_vector<T> &o1, bounded_vector<T> &o2) noexcept]]></prototype>
<p>Swaps the value with <tt>o</tt>.</p>
</synopsis>

<synopsis>
<prototype>T &amp;operator[](size_t i)</prototype>
<prototype>const T &amp;operator[](size_t i) const</prototype>
<p>Access to the elements by index.</p>
<precondition><tt>i &lt; size()</tt></precondition>
</synopsis>

<synopsis>
<prototype>T &amp;front()</prototype>
<prototype>const T &amp;front() const</prototype>
<prototype>T &amp;back()</prototype>
<prototype>const T &amp;back() const</prototype>
<p>Access to the first and the last elements.</p>
<precondition><tt>!empty()</tt></precondition>
</synopsis>

<synopsis>
<prototype>iterator begin()</prototype>
<prototype>const_iterator begin() const</prototype>
<prototype>const_iterator cbegin() const</prototype>
<prototype>iterator end()</prototype>
<prototype>const_iterator end() const</prototype>
<prototype>const_iterator cend() const</prototype>
<p>Access to the elements via iterators.</p>
</synopsis>

</section>

<section><title>Example</title>
<code-block lang="C++"><![CDATA[
// Creating vector for 2 objects of class C
__vic::bounded_vector<C> v(2);

// Creating new object in C++98 mode:
new(v.alloc()) C(...); // Request memory and construct the object
v.push_allocated();    // Fixate successfully created object in the container

// Creating new object in C++11 mode:
v.emplace_back(...);
]]></code-block>
</section>

</chapter>

</chapter>
